//#define _CRT_SECURE_NO_WARNINGS 1
//#include <climits>
//#include <algorithm>
//#include <iostream>
//
//const int V = 12;
//
////int graph[V][V] = {
////    {0, 9, 7, 3, 2, 0, 0, 0, 0, 0, 0, 0}, //1
////    {0, 0, 0, 0, 0, 4, 2, 1, 0, 0, 0, 0},
////    {0, 0, 0, 0, 0, 2, 7, 0, 0, 0, 0, 0},
////    {0, 0, 0, 0, 0, 0, 0, 11, 0, 0, 0, 0},
////    {0, 0, 0, 0, 0, 0, 11, 8, 0, 0, 0, 0}, //5
////    {0, 0, 0, 0, 0, 0, 0, 0, 6, 5, 0, 0},
////    {0, 0, 0, 0, 0, 0, 0, 0, 4, 3, 0, 0},
////    {0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 6, 0},  //8
////    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4},
////    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2},
////    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, INT_MAX},
////    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
////};
//
//int graph[V][V] = {
//    {0, 9, 7, 3, 2, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX},
//    {INT_MAX, 0, INT_MAX, INT_MAX, INT_MAX, 4, 2, 1, INT_MAX, INT_MAX, INT_MAX, INT_MAX},
//    {INT_MAX, INT_MAX, 0, INT_MAX, INT_MAX, 2, 7, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX},
//    {INT_MAX, INT_MAX, INT_MAX, 0, INT_MAX, INT_MAX, INT_MAX, 11, INT_MAX, INT_MAX, INT_MAX, INT_MAX},
//    {INT_MAX, INT_MAX, INT_MAX, INT_MAX, 0, INT_MAX, 11, 8, INT_MAX, INT_MAX, INT_MAX, INT_MAX},
//    {INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, 0, INT_MAX, INT_MAX, 6, 5, INT_MAX, INT_MAX},
//    {INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, 0, INT_MAX, 4, 3, INT_MAX, INT_MAX},
//    {INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, 0, INT_MAX, 5, 6, INT_MAX},
//    {INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, 0, INT_MAX, INT_MAX, 4},
//    {INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, 0, INT_MAX, 2},
//    {INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, 0, INT_MAX},
//    {INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, INT_MAX, 0}
//};

//void floydWarshall() {
//    int dist[V][V];
//
//    for (int i = 0; i < V; i++)
//        for (int j = 0; j < V; j++)
//            dist[i][j] = graph[i][j];
//
//    for (int k = 0; k < V; k++)
//        for (int i = 0; i < V; i++)
//            for (int j = 0; j < V; j++)
//                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX)
//                    dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
//
//    // print the shortest distance matrix
//    for (int i = 0; i < V; i++) {
//        for (int j = 0; j < V; j++) {
//            if (dist[i][j] == INT_MAX)
//                std::cout << "INF ";
//            else
//                std::cout << dist[i][j] << "   ";
//        }
//        std::cout << std::endl;
//    }
//}

//int main() {
//    floydWarshall();
//    return 0;
//}